#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>
#include "AVLTree.h"

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        int n = nums.size();

        for (int i = 0; i < n - 2; i++)
        {
            int l = i + 1, r = n - 1, target = -nums[i];
            while (l < r)
            {
                if (nums[l] + nums[r] > target) r--;
                else if (nums[l] + nums[r] < target) l++;
                else
                {
                    ret.push_back({ nums[i], nums[l], nums[r] });
                    while (l < r && nums[l + 1] == nums[l++]);
                    while (l < r && nums[r - 1] == nums[r--]);
                }
            }
            while (i < n - 2 && nums[i + 1] == nums[i]) i++;
        }

        return ret;
    }
};
int main()
{
    vector<int> nums = { -1,0,1,2,-1,-4 };
    Solution().threeSum(nums);
	return 0;
}